package com.kdg.arithmetic;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 直接插入排序
 * 由此时间复杂度最高为n^2
 * Created by kong on 2018/5/21.
 */
public class StraightInsertionSort {

    private static Logger logger = LoggerFactory.getLogger(StraightInsertionSort.class);

    public static void main(String[] args) throws InterruptedException {
        int a[] = {23, 12, 35, 68, 4, 3, 5, 90};
        insertSort(a);
    }

    /**
     * 打印
     *
     * @param a
     */
    private static void printSort(int[] a) {
        if (a.length > 0) {
            for (int i : a) {
                System.out.print(i + " ");
            }
        }
    }

    /**
     * 直接插入排序
     *
     * @param a
     */
    private static void insertSort(int[] a) throws InterruptedException {
        if (a.length > 0) {
            for (int i = 1; i < a.length; i++) {
                int x = a[i];
                int j;
                for (j = i; j > 0 && a[j - 1] > x; j--) {
                    logger.info("将a[j-1]值"+a[j-1]+"下标从"+(j-1)+"后移到"+j);
                    a[j] = a[j-1];
                    Thread.sleep(500);
                }
                a[j] = x;
            }
            printSort(a);
        }
    }
}
